class Solution:
    def sortString(self, s: str) -> str:
        data = []
        tmp = list(s)
        while tmp:
            # 第一步
            first = tmp[0]
            for i in tmp:
                first = min(first, i)
            data.append(first)
            tmp.remove(first)

            # 第二步  s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
            while 1:
                if not tmp:
                    break
                second = None
                for i in tmp:
                    if i > data[-1]:
                        if not second:
                            second = i
                        else:
                            second = min(second, i)
                if second:
                    data.append(second)
                    tmp.remove(second)
                else:
                    break

            # 从 s 中选出 最大 的字符，将它 接在 结果字符串的后面
            # print("data=",data)
            if not tmp:
                break
            fouth = max(tmp)
            data.append(fouth)
            tmp.remove(fouth)

            # 5. 从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
            while 1:
                if not tmp:
                    break
                firth = None
                for i in tmp:
                    if i < data[-1]:
                        if not firth:
                            firth = i
                        else:
                            firth = max(firth, i)
                if firth:
                    data.append(firth)
                    tmp.remove(firth)
                else:
                    break

            # 重复步骤 5 ，直到你没法从 s 中选择字符。

            # 复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
        return "".join(data)

if __name__ == "__main__":
    print(Solution().sortString("aaaabbbbcccc"))
    print(Solution().sortString("aaaabbbbcccc") == "abccbaabccba")
    print(Solution().sortString("rat") == "art")
    print(Solution().sortString("ggggggg") == "ggggggg")
    print(Solution().sortString("spo") == "ops")
    print(Solution().sortString("") == "")
        